package cn.hesion.leetcode;
/**
 * ClassName: PrintTree <br/>
 * Description: <br/>
 * date: 2022/6/15 21:46<br/>
 *
 * @author Hesion<br />
 * @version
 * @since JDK 1.8
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author: hesion
 * @create: 2022-06-15 21:46
 **/
public class PrintTree {
    public int getTreeHight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(getTreeHight(root.left), getTreeHight(root.right))+ 1;
    }

    void dfs(int H, int d, int p, TreeNode root, List<List<String>> ret) {
        if (root == null) {
            return;
        }
        int linenum = p - (1 << d);
        int first = (1 << (H - 1 - d)) - 1;
        int command = 1 << (H - 1 - d + 1);
        int col = first + (linenum) * command;
        int row = d;
        ret.get(row).set(col, root.val + "");
        dfs(H, d + 1, p << 1, root.left, ret);
        dfs(H, d + 1, p << 1 | 1, root.right, ret);
    }

    public List<List<String>> printTree(TreeNode root) {
        //获取到树的高度
        int h = getTreeHight(root);
        int n = (1 << h) - 1;
        int m = h;
        List<List<String>> ret = new ArrayList<List<String>>();
        for (int i = 0; i < m; i++) {
            List<String> ans = new ArrayList<String>();
            for (int j = 0; j < n; ++j) {
                ans.add("");
            }
            ret.add(ans);
        }
        dfs(h, 0, 1, root, ret);
        return ret;
    }

}
